package com.zzy.algorithm.sort;

import com.zzy.algorithm.model.PrintArray;

import java.util.ArrayList;
import java.util.List;

/**
 * 基数排序
 */
public class Q34_RadixSort {

    public static int[] nums = new int[]{5,7,1,2,8,9,3};

    public static void main(String[] args) {
        radixSort(nums);
        for(int x : nums){
            System.out.println(x);
        }
    }

    private static int[] radixSort(int[] nums){
        if(nums == null || nums.length < 2){
            return nums;
        }
        //找出最大数
        int max = nums[0];
        for(int i = 1; i <nums.length;i++){
            max = Math.max(max,nums[i]);
        }
        //先算出最大数的位数，它决定了我们要进行几轮排序
        int maxDignit = 0;
        while (max != 0){
            max /= 10;
            maxDignit++;
        }
        int mod = 10,div = 2;
        //构建桶
        List<List<Integer>> bucketList = new ArrayList<>();
        for(int i = 0 ; i < mod ;i++){
            bucketList.add(new ArrayList<>());
        }
        //按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照关键字对数组排序
        for(int i = 0; i < maxDignit;i++,mod *= 10,div *= 10){
            //遍历原始数组，放入桶找那个
            for(int j = 0 ; j < nums.length ; j++){
                int num = (nums[j] % mod) / div;
                bucketList.get(num).add(nums[j]);
            }
            //桶中的数据写会原始数组，清除桶，准备下一轮的排序
            int index = 0;
            for(int j = 0 ; j < bucketList.size() ;j++){
                for(int k = 0; k < bucketList.get(j).size();k++){
                    nums[index++] = bucketList.get(j).get(k);
                }
                bucketList.get(j).clear();
            }
        }
        return nums;
    }

}
